#pragma once
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

class unordered_list
{
private:
	struct node
	{
		string data;
		node *next;

		node(string data = "", node *next = nullptr)
		{
			this->data = data;
			this->next = next;
		}
	};

	node *head;
	node *freehead;

	void copy_from(unordered_list &that)
	{
		node *tail = head = freehead = nullptr;
		node *n = that.head;
		while (n != nullptr)
		{
			if (head == nullptr)
				head = tail = new node(n->data);
			else
				tail = tail->next = new node(n->data);
			n = n->next;
		}
		n = that.freehead;
		while (n != nullptr)
		{
			freehead = new node("", freehead);
			n = n->next;
		}
	}

	void clear_mem()
	{
		while (head != nullptr)
		{
			node *d = head;
			head = head->next;
			delete d;
		}
		while (freehead != nullptr)
		{
			node *d = freehead;
			freehead = freehead->next;
			delete d;
		}
	}
public:

	unordered_list(int size_free_list = 0) : head(nullptr), freehead(nullptr)
	{
		for (int i = 0; i < size_free_list; i++)
			freehead = new node("", freehead);
	}

	unordered_list(unordered_list &that)
	{
		copy_from(that);
	}

	~unordered_list()
	{
		clear_mem();
	}

	unordered_list& operator=(unordered_list &that)
	{
		if (!empty())
			clear_mem();
		copy_from(that);
		return *this;
	}

	bool empty() { return head == nullptr; }

	int free_list_size() 
	{
		node *n = freehead;
		int i = 0;
		while (n != nullptr)
		{
			i++;
			n = n->next;
		}
		return i;
	}

	void add(string data)
	{
		if (freehead != nullptr)
		{
			node *n = freehead;
			freehead = freehead->next;
			n->data = data;
			n->next = head;
			head = n;
		}
		else
		{
			head = new node(data, head);
		}
	}

	string print()
	{
		ostringstream oss;
		node *n = head;
		while (n != nullptr)
		{
			oss << n->data;
			if (n->next != nullptr)
				oss << ",";
			n = n->next;
		}
		return oss.str();
	}

	void clear()
	{
		while (head != nullptr)
		{
			node *n = head;
			head = head->next;
			n->data = "";
			n->next = freehead;
			freehead = n;
		}
	}

	void remove(string data)
	{
		node *p = nullptr;
		node *n = head;
		while (n != nullptr)
		{
			if (n->data.compare(data) == 0)
			{
				if (n == head)				 //first node
					head = head->next;
				else if (n->next == nullptr) //last node
					p->next = nullptr;
				else						 //inner node
					p->next = n->next;
				n->data = "";
				n->next = freehead;
				freehead = n;
				break;
			}
			else
			{
				p = n;
				n = n->next;
			}
		}
	}

	node* search(string data)
	{
		node *p = nullptr;
		node *n = head;
		while (n != nullptr)
		{
			if (n->data.compare(data) == 0)
			{
				if (n == head)				 //first node
					return n;
				else if (n->next == nullptr) //last node
				{
					p->next = nullptr;
					n->next = head;
					head = n;
					return n;
				}
				else						 //inner node
				{
					p->next = n->next;
					n->next = head;
					head = n;
					return n;
				}
			}
			else
			{
				p = n;
				n = n->next;
			}
		}
	}

	class iterator
	{
	public:
		typedef iterator self_type;
		typedef node value_type;
		typedef node* pointer;
		typedef node& reference;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		iterator(pointer ptr_) { this->ptr_ = ptr_; }

		self_type operator++()
		{
			self_type i = *this;
			ptr_ = ptr_->next;
			return i;
		}

		self_type operator++(int junk)
		{
			ptr_ = ptr_->next;
			return *this;
		}

		bool operator==(const self_type& rop) { return ptr_ == rop.ptr_; }
		bool operator!=(const self_type& rop) { return ptr_ != rop.ptr_; }

		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }

	private:
		pointer ptr_;
	};

	iterator begin() { return iterator(head); }
	iterator end() { return iterator(nullptr); }
};

